//https://www.nowcoder.com/practice/046a55e6cd274cffb88fc32dba695668?tpId=13&tqId=1024831&ru=%2Fpractice%2F48d2ff79b8564c40a50fa79f9d5fa9c7&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
// 思路：动态规划：f[n] = f[n-1] + f[n-2]*[0,1]

#include <iostream>
#include <vector>
#include <set>
#include <queue>

using namespace std;

#include <cstddef>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    int solve(string nums) {
        // write code here
        if (nums.empty() || nums[0] == '0') {
            return 0 ;
        }
        if (nums.size() == 1) return 1;
        //当0的前面不是1或2时，无法译码，0种
        for (int i = 1; i < nums.length(); i++) {
            if (nums[i] == '0')
                if (nums[i - 1] != '1' && nums[i - 1] != '2')
                    return 0;
        }
        size_t total = 0;
        // 动态规划 f[n] = f[n-1] + f[n-2]*[0,1]
        // 辅助数组初始化为1
        //"31717126241541717"
        vector<int> dp(nums.length(),0);
        dp[0]=1;
        for(int i = 1;i<dp.size();++i){
            if ((nums[i-1]=='1' && nums[i] !='0' )|| (nums[i-1]=='2' && nums[i] > '0' &&nums[i] < '7')) {
                if (i-2 <0) {
                    dp[i] = 2;
                } else {
                    dp[i] =dp[i-1]+dp[i-2];
                }
            }else{
                dp[i]=dp[i-1] ;
            }

        }
        return dp[nums.size()-1];
    }
};